import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.Random;
import java.util.Vector;

public class Pollard {
	
	public static Kattio io;
	public static BigInteger constants[]= new BigInteger[]{BigInteger.ONE, new BigInteger("2"), new BigInteger("3"), new BigInteger("5"), new BigInteger("7"), new BigInteger("11"), new BigInteger("13")};
	long start_time;
	Vector<BigInteger> factors;
	static final long time_limit = 260L;
	static final long time_limit_NR = 260L;
	
	
	public Pollard(Kattio io, long start_time, Vector<BigInteger> factors){
		this.io = io;
		this.start_time = start_time;
		this.factors = factors;
	}
	
	//Is recursively called until only prime numbers remain. Prime numbers are printed. 
	public void factor(BigInteger n){
			
			if(n.isProbablePrime(5)){
				//io.println(n);
				factors.add(n);
			}
			else{
				BigInteger f1;
				BigInteger f2;
				
				//f1 = pollard(n);
				f1 = brent(n);
				
				if(f1.equals(BigInteger.ONE)){
					BigInteger ans[] = specialCase(n);
					
					if(ans == null){
						//io.println("fail");
						factors.add(BigInteger.ONE);
					}
					else{
						BigInteger i = BigInteger.ZERO;
						while(i.compareTo(ans[1]) < 0){
							factor(ans[0]);
							i = i.add(BigInteger.ONE);
						}
					}
				}
				else{
					f2 = n.divide(f1);
					factor(f1);
					factor(f2);
				}
			}
	}
	
	public BigInteger brent(BigInteger n){
		for(int test=0;test< constants.length;test++){
			Random rnd = new Random();
			BigInteger two = new BigInteger("2");
			//BigInteger y = new BigInteger(n.bitLength(), rnd);
			BigInteger y = BigInteger.ZERO;
			//BigInteger c = new BigInteger(n.bitLength(), rnd);
			BigInteger c = constants[test];
			//BigInteger m = new BigInteger(n.bitLength(), rnd);
			BigInteger m = BigInteger.ONE;
			
			BigInteger g = BigInteger.ONE;
			BigInteger r = BigInteger.ONE;
			BigInteger q = BigInteger.ONE;
			
			BigInteger x = y;
			BigInteger ys = y;
			
			if(n.mod(two).equals(BigInteger.ZERO)) return two;
			else{
				while(g.equals(BigInteger.ONE)){
					if(System.currentTimeMillis() - start_time > time_limit){
						return BigInteger.ONE;
					}
					x = y;
					for(BigInteger i = BigInteger.ZERO; i.compareTo(r) < 0; i = i.add(BigInteger.ONE)){
						//y = f(y, c, n);
						y = y.multiply(y).add(c).mod(n);
					}
					BigInteger k = BigInteger.ZERO;
					while(k.compareTo(r) < 0 && g.equals(BigInteger.ONE)){
						if(System.currentTimeMillis() - start_time > time_limit){
							return BigInteger.ONE;
						}
						ys = y;
						for(BigInteger i = BigInteger.ZERO; i.compareTo(m.min(r.subtract(k))) < 0; i = i.add(BigInteger.ONE)){
							//y = f(y, c, n);
							y = y.multiply(y).add(c).mod(n);
							q = q.multiply(x.subtract(y).abs()).mod(n);
						}
						g = q.gcd(n);
						k = k.add(m);
					}
					r = r.multiply(two);
				}
				/*
				if(g.equals(n)){
					//return BigInteger.ONE;
					while(true){
						if(System.nanoTime() - start_time > 900000000L){
							return BigInteger.ONE;
						}
						//ys = f(ys, c, n);
						ys = ys.multiply(ys).add(c).mod(n);
						g = n.gcd(x.subtract(ys).abs());
						if(g.compareTo(BigInteger.ONE) > 0) break;
					}
				}*/
				
			}
			if(g.compareTo(n) != 0)
				return g;
			//else return BigInteger.ONE;
		}
		return BigInteger.ONE;
	}
	
	
	
	
	public BigInteger pollard(BigInteger n){
		
		for(int i=0;i< constants.length;i++){
			BigInteger x = new BigInteger("2");
			BigInteger y = new BigInteger("2");

			BigInteger d = BigInteger.ONE;
			
			while(d.equals(BigInteger.ONE)){
				if(System.currentTimeMillis() - start_time > time_limit){
					return BigInteger.ONE;
				}
				//x = f(x, n, c);
				//y = f(f(y, n, c), n, c);
				x = f(x, n, constants[i]);
				y = f(f(y, n, constants[i]), n, constants[i]);
				d = x.subtract(y).gcd(n);
			}
			//if(d != n) return d;
			if(d.compareTo(n) != 0) return d;
		}
		return BigInteger.ONE;
	}
	
	private BigInteger f(BigInteger x, BigInteger n, BigInteger c){
		return x.multiply(x).add(c).mod(n);
	}
	

	
	public void tests(){
		System.out.println("testcode prints:");
		//41^200
		
		BigInteger[] ans = specialCase(new BigInteger("36038884832714017120583374584411861606378840490608984539340290142838458875879085141406049716103582183859419972236396635537081068318342030360034865620257521231674461014960871415155255611180161167314287707104892085605388693472830726263449752273518705705062597575741512283162442923684120796580363832366938838844219390457448001"));
		if(ans != null){
			System.out.println("a = " + ans[0]);
			System.out.println("k = " + ans[1]);
		}
		else{
			System.out.println("ans == null");
		}
		
		//104729^11
		
		ans = specialCase(new BigInteger("16624038034347586883296534058797261637560142646943747529"));
		if(ans != null){
			System.out.println("a = " + ans[0]);
			System.out.println("k = " + ans[1]);
		}
		else{
			System.out.println("ans == null");
		}
		
		//random number that is not a a^k number
		ans = specialCase(new BigInteger("16624038034347586883296534058797261637560142646943747530"));
		if(ans != null){
			System.out.println("a = " + ans[0]);
			System.out.println("k = " + ans[1]);
		}
		else{
			System.out.println("ans == null");
		}
	}
	
	/*
	 * Testar om n = a^k, ger isf ut {a,k} , annars null
	 * 
	 */
	private BigInteger[] specialCase(BigInteger n){
		
		for(int k= 2; k< 1000; k++){
			//System.out.println("testing k = "+k);
			if(System.currentTimeMillis() - start_time > time_limit_NR){
				return null;
			}
			if(new BigInteger("2").pow(k).compareTo(n) > 0){
				break;
			}
			BigInteger temp = newtonRaphson(n, k, new BigInteger("100"));
			if(temp != null){
				return new BigInteger[]{temp, new BigInteger(Integer.toString(k))};
			}
		}
		return null;
	}
	
	private BigInteger newtonRaphson(BigInteger n,int k, BigInteger start_x){
		BigDecimal n_dec = new BigDecimal(n);
		BigDecimal old_x = new BigDecimal(start_x);
		BigDecimal k_dec = new BigDecimal(Integer.toString(k));
		
		int counter = 0;
		while(true){
			if(System.currentTimeMillis() - start_time > time_limit_NR){
				return null;
			}
			BigDecimal new_x = old_x.subtract(old_x.divide(k_dec, RoundingMode.HALF_EVEN )).add(n_dec.divide(k_dec.multiply(old_x.pow(k-1)), RoundingMode.HALF_EVEN));
			
			//System.out.println(new_x);
		
			if(new_x.toBigInteger().pow(k).compareTo(n) == 0){
				return new_x.toBigInteger();
			}
			else if(counter > 1000){
				return null;
			}
			old_x = new_x.setScale(5, RoundingMode.DOWN);
			counter++;
		}
		
	}
	
}
